Algebraic decoders may use operations on Galois Field elements to decode error correction codes. The operations typically include extracting a cubic root of an element, and methods for such extraction are known in the art. For example, U.S. Pat. No. 6,199,188, to Shen et al., whose disclosure is incorporated herein by reference, provides functional block diagrams of systems for determining the cube roots of elements of GF(2m+1) and GF(22m).
U.S. Pat. No. 5,761,102, to Weng, whose disclosure is incorporated herein by reference, describes a system and method for determining the cube root of an element α3k of a Galois Field GF(22m). In determining the cube root, the system uses a look-up table to determine the cube root of α3k(2m±1).
U.S. Pat. No. 5,905,740, to Williamson, whose disclosure is incorporated herein by reference, describes a cube root computation that utilizes logarithmic and anti-logarithmic tables as well as a division by 3 module.
An article titled “Efficient Computation of Roots in Finite Fields,” by Barreto et al., and published in Designs, Codes and Cryptography, May 2006, Volume 39, is incorporated herein by reference. The article provides an algorithm that computes rth roots of an element of a Galois Field GF(qm) provided that q, m, r satisfy certain constraints.
Documents incorporated by reference in the present patent application are to be considered an integral part of the application except that to the extent any terms are defined in these incorporated documents in a manner that conflicts with the definitions made explicitly or implicitly in the present specification, only the definitions in the present specification should be considered.